import java.util.Arrays;
import java.util.Stack;

public class Main {
    private static int partition(int[] array,int left,int right){  //快排挖坑法
        int key = array[left];
        int i = left;
        while (left < right){
            while (left < right && array[right] >= key){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }

    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int piovt = partition(array,left,right);
        if (piovt-1 > left){
            stack.push(left);
            stack.push(piovt-1);
        }
        if (piovt+1 < right){
            stack.push(piovt+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            if (piovt-1 > left){
                stack.push(left);
                stack.push(piovt-1);
            }
            if (piovt+1 < right){
                stack.push(piovt+1);
                stack.push(right);
            }
        }
    }

    public static void margeSort(int[] array){ //分治法
        int left = 0;
        int right = array.length-1;
        margeSortFunc(array,left,right);
    }
    public static void margeSortFunc(int[] array,int left,int right){
        if (left >= right){
            return;
        }
        int mid = (left+right) / 2;
        margeSortFunc(array,left,mid);
        margeSortFunc(array,mid+1,right);
        marge(array,left,right,mid);
    }

    private static void marge(int[] array, int left, int right, int mid) { //合并方法
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        int[] tmpArr = new int[right-left+1];
        while (s1 <= e1 && s2 <= e2){ //判断两个数组都有数据
            if (array[s2] <= array[s1]){
                tmpArr[k] = array[s2];
                k++;
                s2++;
            }else {
                tmpArr[k] = array[s1];
            }
        }
        while (s1 < e1){ //判断其中一个合并项中是否每个元素都大于第二个合并项的所有值
            tmpArr[k++] = array[s1++];
        }
        while (s2 < e2){
            tmpArr[k++] = array[s2++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

    public static void margeSortNor(int[] array){
        int gap = 1;
        while (gap < array.length){ //组数小于数组中元素的个数时
            for (int i = 0; i < array.length; i += 2*gap) {
                int left = i;
                int mid = left+gap-1;
                int right = mid + gap;
                if (mid >= array.length){
                    mid = array.length-1;
                }
                if (right >= array.length){
                    right = array.length-1;
                }
                marge(array,left,right,mid);
            }
            gap *= 2;
        }
    }
    public static void main(String[] args) {
        int[] array = {1,21,32,4,5,8,10,9,8};
        margeSortNor(array);
        System.out.println(Arrays.toString(array));
    }
}